Real-time performance is essential for time-critical responses required in high-performance applications such as telecommunications switching equipment, medical monitoring equipment, space navigation and guidance, and the like. Such applications must deliver responses within specified time parameters in real-time.
Real-time performance is typically provided by operating systems that use thread scheduling mechanisms. Such mechanisms schedule threads for execution on a thread priority basis. For example, Microsoft's WINDOWS CE® operating system provides two-hundred-fifty-six (256) priority levels in a basic round-robin scheduler. Threads of higher priority always run before threads of lower priority. Threads of equal priority run in a first-in-first-out round-robin fashion. For example, thread A runs, then thread B runs, followed by thread C, and back to thread A.
Thread scheduling mechanisms typically use a hardware timer to produce a system tick to determine a maximum amount of time or “quantum” of time that a thread can run in the system without being preempted. When a timer reaches the quantum of time, a thread is preempted to determine if there are other threads of equal or higher priority to execute, or run. The system tick is the rate at which a hardware timer interrupt is generated and serviced by the operating system. When the timer fires, the operating system (OS) schedules a new thread for execution if one is ready to be scheduled. Thus, a thread's quantum is a multiple of the time between system ticks.
For example, FIG. 1 is a graph 100 that shows the relationship between thread execution and thread preemption. The vertical axis 101 represents a number of threads 102-1 through 102-N that are in queue for execution. The horizontal axis 103 represents the passage of time to illustrate servicing by the operating system of the system tick 104, which in turn results in a thread being scheduled and/or preempted if there are any threads ready to be scheduled. A system tick occurs once every time interval 106. The time interval can be any duration of time that is supported by a hardware timer, such as 10 milliseconds.
In this example, all threads 102 are of the same priority. In response to a first system tick 104-1, the scheduler executes thread 102-1 for time duration 106-1. The amount of time that a thread 102 will execute before being preempted to determine if there are any other threads to execute is known as a “thread quantum”. Thus, each time interval 106 represents the thread quantum. The system tick is generated every thread quantum.
In response to system tick 104-2, the scheduler preempts the execution of thread 102-1 to run thread 102-2 for time duration 106-2. In response to system tick 104-3, the scheduler preempts the execution of thread 102-2 to run thread 102- . . . for time duration 106- . . . . In this manner, threads are scheduled and executed by a real-time operating system.
If there are no threads ready to be scheduled, meaning that all threads are blocked in the system, there is no work for an operating system to perform. All threads may be blocked in a system because threads often have to wait for one or more events to occur before continuing to execute. Such events include waiting for another thread to release a resource such as a file, waiting for a key-press event, or waiting for an amount of time to pass. Thus, a thread will often yield processor control to the thread scheduler by placing itself into a yield, inactive, or sleep state for a specified time period, such as a certain number of milliseconds before continuing execution.
A thread that specifies that it wants to yield or sleep for a millisecond (“sleep (1)”) returns or “wakes up” on a system timer tick. If the system timer tick is set to 25 milliseconds, a sleep (1) would result in the thread yielding for at least 1 millisecond, but perhaps yielding up to 25 milliseconds because the timer is set to fire at 25 millisecond intervals. Thus, this thread will not be provided with the scheduling accuracy that it specified—in this example, a millisecond-resulting in poor real-time performance. However, if the system timer interrupt were fired every millisecond, a thread issuing a sleep (1) command would result in the thread sleeping for only a millisecond, which would be the precise amount of time that the thread requested to sleep. Of course, this is dependent on the priority of the thread, and the priority of other threads. This smaller system timer tick value of a millisecond provides the thread's specified scheduling accuracy, which results in higher real-time performance as compared with a scenario where the system tick is set to a larger value.
When there are no threads to schedule, the operating system typically saves power by deactivating or turning off the system's central processing unit (CPU) to place the operating system into an Idle state. The issuance of a system timer tick forces the operating system out of the Idle state by turning the CPU back on so that the operating system can determine if there are any new threads that are ready to be scheduled.
If no threads are ready to be scheduled, the operating system again places itself into an Idle state. Significantly, the frequency at which the system timer tick fires determines how often the system transitions from the Idle state to activate the operating system to determine if there are any threads to schedule. In other words, the amount of time between consecutive system ticks is also the amount of time that the operating system is deactivated when the system is in an Idle state. This amount of time is traditionally static and does not change. Thus, traditional systems typically use static idle time scheduling mechanisms.
Setting the system timer to a millisecond to obtain substantial real-time performance means that if there are no threads to schedule, the system will leave an Idle state every millisecond to activate the operating system to determine if there are any threads to schedule. Upon making this transition, the operating system may determine that there are no new threads to schedule, whereupon the operating system will again be deactivated for a millisecond by placing the system into the Idle state. The process of resuming the operating system when there are no new threads to reschedule is a power consuming process. On a battery-powered device, such transitions use valuable battery life and result in the depletion of limited power reserves.
Consumers are aware about the battery life of a product as the battery life can make or break a product's acceptance in the marketplace. Thus, OEMs and embedded developers, especially those involved in power management of battery powered devices, are concerned with the power efficiency aspects that are a consequence of a system timer interrupt firing every millisecond-especially when the system is idle.
To conserve battery power, OEMs typically preset the system timer, or thread quantum, to a constant of ten (10) milliseconds or greater to preserve the limited battery reserves on battery powered devices. However, as discussed above, increasing the value of the system timer in this manner results in poor real-time performance of time-critical applications because threads may not be provided with the scheduling accuracy required of such applications.
In light of the above, a system is needed that provides real-time thread scheduling performance essential to time-critical responses in high-performance applications without increasing power consumption.